package com.yubest;

import java.util.LinkedList;

/**
 * 给你二叉树的根结点 root ，请你将它展开为一个单链表：
 *
 * 展开后的单链表应该同样使用 TreeNode ，其中 right 子指针指向链表中下一个结点，而左子指针始终为 null 。
 * 展开后的单链表应该与二叉树 先序遍历 顺序相同。
 *  
 *
 * 示例 1：[图片] img/0114.jpg
 *
 *
 * 输入：root = [1,2,5,3,4,null,6]
 * 输出：[1,null,2,null,3,null,4,null,5,null,6]
 * 示例 2：
 *
 * 输入：root = []
 * 输出：[]
 * 示例 3：
 *
 * 输入：root = [0]
 * 输出：[0]
 *  
 *
 * 提示：
 *
 * 树中结点数在范围 [0, 2000] 内
 * -100 <= Node.val <= 100
 *  
 *
 * 进阶：你可以使用原地算法（O(1) 额外空间）展开这棵树吗？
 *
 * 来源：力扣（LeetCode）
 * 链接：https://leetcode-cn.com/problems/flatten-binary-tree-to-linked-list
 * 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
 *
 * @Author hweiyu
 * @Description
 * @Date 2022/1/17 9:59
 */
public class P0114 {
}

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode() {}
 *     TreeNode(int val) { this.val = val; }
 *     TreeNode(int val, TreeNode left, TreeNode right) {
 *         this.val = val;
 *         this.left = left;
 *         this.right = right;
 *     }
 * }
 */
class Solution114 {

    /**
     * 思路：栈
     * @param root
     */
    public void flatten(TreeNode root) {
        if (null == root) {
            return;
        }
        TreeNode pre = null, cur = null;
        LinkedList<TreeNode> list = new LinkedList<>();
        list.addLast(root);
        while (!list.isEmpty()) {
            cur = list.pollFirst();
            if (cur.right != null) {
                list.addFirst(cur.right);
            }
            if (cur.left != null) {
                list.addFirst(cur.left);
            }
            if (pre != null) {
                pre.left = null;
                pre.right = cur;
            }
            pre = cur;
        }
    }

    /**
     * 思路：寻找前驱节点，该节点的左子树中最后一个被访问的节点是左子树中的最右边的节点，也是该节点的前驱节点。因此，问题转化成寻找当前节点的前驱节点。
     *
     * 1、寻找前驱节点
     * 2、将当前节点的右孩子移动为前驱节点的右孩子
     * 3、将当前节点的左孩子移动为当前节点的右孩子
     * 4、将当前节点的左孩子置为空
     *
     * @param root
     */
    public void flatten2(TreeNode root) {
        if (null == root) {
            return;
        }
        TreeNode cur = root, preCur = null;
        while (cur != null) {
            preCur = cur.left;
            if (null != preCur) {
                while (preCur.right != null && preCur.right != cur) {
                    preCur = preCur.right;
                }
                preCur.right = cur.right;
                cur.right = cur.left;
                cur.left = null;
            }
            cur = cur.right;
        }
    }
}
